1. Field of the Invention
The present invention relates to the field of URL look-ups and, more particularly, to a technique for finding REST resources and constraints using an n-ary tree structure navigated using a collision free progressive hash.
2. Description of the Related Art
U.S. Published Patent Application No. 20050055437-A1, U.S. Pat. No. 7,523,171, entitled “Multidimensional Hashed Tree Based URL Matching Engine Using Progress Hashing” disclosed a mechanism for matching uniform resource locators (URLs) to resources and/or rules. In this application, each node of a tree structure is associated with a URL portion and includes a multidimensional hash table. These hash tables are established and grown in a manner that ensures no hash collisions occur at each node. Growing such a hash structure ensures quick look-up, although some additional time is sometimes necessary to re-structure a hash table when adding entries to ensure that collisions are avoided. U.S. Published Patent Application No. 20050055437-A1 was primarily directed to a Web 1.0 environment, where URL lookups were needed to find Web site addresses for purposes of serving a Web page associated with that address to a requesting user.
Web 2.0 applications have been changing a manner the Web is being used. Web 1.0 Web resources have traditionally been for information presentation, meaning Web 1.0 was primarily a “read only” computing space from a user perspective. Web 2.0 technologies, however, have caused the Web to evolve into a read, write, update computing space, which has generally been termed Web 2.0. In other words, many Web 2.0 applications, such as Web office productivity applications, collaboration applications, content sharing applications, social networking sites, BLOGS, WIKIS, Mash-ups, and the like have emerged, which depend upon user provided information to increase value to that user and to other users of the Web 2.0 application.
One important standard that defines a manner for retrieving, posting, updating, and deleting Web 2.0 content is the Representational State Transfer (REST) architecture. In a REST architecture, application state and functionality are divided into resources, each of which is uniquely addressable through a URL. REST architectures have client/server separation, which simplifies component implementation, reduces the complexity of connector semantics, improves the effectiveness of performance tuning, and increases scalability. Interactions with REST resources generally involve targeting a resource with a URL, passing the resource one or more parameters, and issuing one of a small set of commands. These commands include GET, POST, PUT, and DELETE, for retrieving, updating, adding, and deleting information, respectively.
In REST implementations, not only must URL's be constantly looked-up in tables, but additional target-specific concerns must be handled as well. For example, many REST resources have a set of constraints associated with them, such as security constraints. Traditionally, URL look-ups and constraint look-ups have been distinct operations, each incurring a distinct implementation cost. Many of the constraints are based upon “pattern matched” rules, or rules that apply to a set of related REST resources and not just to a specific resource itself. What is needed is an efficient mechanism for not only performing a URL lookup, but for also acquiring all pattern based rules and constraints associated with this URL.